package xkp.lesson.utils;

/**
 * ArraysUtils这个工具类包含对数组快速排序、二分查找、for循环遍历打印
 * @author Taoge
 *
 */
public class ArraysUtils {

	/**
	 * 构造方法私有化，因为此处是工具类，所有的方法都可以直接通过类名称
	 * 访问，所以不需要new对象，为了避免new对象，把构造方法私有化
	 */
	private ArraysUtils() {}


	/**
	 *  对整型型数组进行排序
	 * @param arr 要被排序的数组
	 * @param low 本次排序的开始位置
	 * @param high 本次排序的结束位置
	 */
	public static void quickSort(int[] arr,int low,int high) {
		 int i,j,temp,t;
	        if(low>=high){
	            return;
	        }
	        i=low;
	        j=high;
	        //temp就是基准位
	        temp = arr[low];
	 
	        while (i<j) {
	            //先看右边，依次往左递减
	            //右边查找比基准点小的值
	            //同时要注意i与j的值
	            while (temp<=arr[j]&&i<j) {
	                j--;
	            }
	            //再看左边，依次往右递增
	            //左边要找比基准点大的值
	            //同时也要注意i与j的值
	            while (temp>=arr[i]&&i<j) {
	                i++;
	            }
	            //如果满足条件则交换
	            //注意i不能等于j
	            //i==j时没必要交换
	            if (i<j) {
	                t = arr[j];
	                arr[j] = arr[i];
	                arr[i] = t;
	            }
	 
	        }
	        //如果到这一步一定是i==j
	        //最后将基准为与i和j相等位置的数字交换
	         arr[low] = arr[i];
	         arr[i] = temp;
	        //递归调用左半数组
	        quickSort(arr, low, j-1);
	        //递归调用右半数组
	        quickSort(arr, j+1, high);
	}

	/**
	 *  对整型型数组进行排序
	 * @param arr 要被排序的数组
	 * @param low 本次排序的开始位置
	 * @param high 本次排序的结束位置
	 */
	public static void quickSort(double[] arr,int low,int high) {
		 int i,j;
		 double t;
		 double temp;
	        if(low>=high){
	            return;
	        }
	        i=low;
	        j=high;
	        //temp就是基准位
	        temp = arr[low];
	 
	        while (i<j) {
	            //先看右边，依次往左递减
	            //右边查找比基准点小的值
	            //同时要注意i与j的值
	            while (temp<=arr[j]&&i<j) {
	                j--;
	            }
	            //再看左边，依次往右递增
	            //左边要找比基准点大的值
	            //同时也要注意i与j的值
	            while (temp>=arr[i]&&i<j) {
	                i++;
	            }
	            //如果满足条件则交换
	            //注意i不能等于j
	            //i==j时没必要交换
	            if (i<j) {
	                t = arr[j];
	                arr[j] = arr[i];
	                arr[i] = t;
	            }
	 
	        }
	        //如果到这一步一定是i==j
	        //最后将基准为与i和j相等位置的数字交换
	         arr[low] = arr[i];
	         arr[i] = temp;
	        //递归调用左半数组
	        quickSort(arr, low, j-1);
	        //递归调用右半数组
	        quickSort(arr, j+1, high);
	}

	/**
	 * 二分法查找数组
	 * @param arr 要查找的数组
	 * @param key 要查找的值
	 * @return 第一次查到的索引，如果没有查找返回-1
	 */
	public static int binarySearch(int[] arr,int key) {
		 //定义三个索引位置。
        int min = 0;
        int max = arr.length - 1;
        int mid = 0;
        //循环折半，条件， min<=max
        while(min <= max) {
            //公式，计算中间索引
            mid = (min+max)/2;
            //让被找元素和中间索引元素进行比较
            if(key>arr[mid]) {
                min = mid +1;
            }else if(key <arr[mid]) {
                max = mid -1;
            }else {
                //找到元素，返回元素索引
                return mid;
            }
        }
        return -1;
	}
	
	/**
	 * 二分法查找数组
	 * @param arr 要查找的数组
	 * @param key 要查找的值
	 * @return 第一次查到的索引，如果没有查找返回-1
	 */
	public static int binarySearch(double[] arr,double key) {
		 //定义三个索引位置。
        int min = 0;
        int max = arr.length - 1;
        int mid = 0;
        //循环折半，条件， min<=max
        while(min <= max) {
            //公式，计算中间索引
            mid = (min+max)/2;
            //让被找元素和中间索引元素进行比较
            if(key>arr[mid]) {
                min = mid +1;
            }else if(key <arr[mid]) {
                max = mid -1;
            }else {
                //找到元素，返回元素索引
                return mid;
            }
        }
        return -1;
	}
	
	/**
	 * 遍历并打印数组
	 * @param arr 要被打印的数组
	 */
	public static void printArr(int[] arr) {
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"\t");
		}
		System.out.println();
	}
	
	/**
	 * 遍历并打印数组
	 * @param arr 要被打印的数组
	 */
	public static void printArr(double[] arr) {
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+"\t");
		}
		System.out.println();
	}

	
	/**
	 * 冒泡排序
	 * @param arr  需要被排序的数组
	 */
	public static void maopao(int[] arr) {
		for(int i = 0; i< arr.length-1; i++) {
			for(int j = 0; j < arr.length-1-i; j++) {
				if(arr[j]>arr[j+1]) {
					//此处直接操作原数组进行交换
					int temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}
			}
		}
	
	}

	
	/**
	 * 冒泡排序
	 * @param arr  需要被排序的数组
	 */
	public static void maopao(double[] arr) {
		for(int i = 0; i< arr.length-1; i++) {
			for(int j = 0; j < arr.length-1-i; j++) {
				if(arr[j]>arr[j+1]) {
					//此处直接操作原数组进行交换
					double temp = arr[j+1];
					arr[j+1] = arr[j];
					arr[j] = temp;
				}
			}
		}
	
	}

}
